public class BinarySearchTree {
    /**
     * 特点：
     *  1，树中所有节点值均不重复
     *  2，可以高效进行搜索*/

    public TreeNode root;

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public boolean insert(int val) {
        /**
         * 在二叉搜索树中插入节点
         * */
        TreeNode newNode = new TreeNode(val);

        // 1 判空
        if(root == null) {
            root = newNode;
        } else {
            // 2 找到合适的插入点
            TreeNode cur = root;
            TreeNode prev = null;
            while(cur != null) {
                if(cur.val > val) {
                    // 左边
                    prev = cur;
                    cur = cur.left;
                } else if(cur.val < val) {
                    // 右边
                    prev = cur;
                    cur = cur.right;
                } else {
                    // 等于，预期之外的结构（二叉搜索树中不允许存在重复的值）
                    return false;
                }
            }
            // 3 根据值判断
            if(prev.val > val) {
                prev.left = newNode;
            } else {
                prev.right = newNode;
            }
        }
        return true;
    }

    public boolean search(int val) {
        /**
         * 在二叉搜索树中查找指定值*/
        TreeNode cur = root;
        while(cur != null && cur.val != val) {
            if(cur.val > val) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        if(cur == null) {
            return false;
        } else {
            return true;
        }
    }

    public boolean remove(int val) {
        /**
         * 在二叉搜索树中删除指定值所在节点，并保持其依旧为二叉搜索树
         * 此方法为查找目标值是否存在于搜索树中，若是存在，则传递删除节点和父节点进行删除；若是不存在，则返回false*/
        TreeNode parent = null;
        TreeNode cur = root;
        while(cur != null) {
            if(cur.val > val) {
                parent = cur;
                cur = cur.left;
            } else if(cur.val < val) {
                parent = cur;
                cur = cur.right;
            } else {
                removeSupport(cur, parent);
                return true;
            }
        }
        return false;
    }

    private void removeSupport(TreeNode cur, TreeNode parent) {
        /**
         * 使用替换法在二叉搜索树中删除指定节点
         * @parameter cur：待删除节点
         * @parameter parent：待删除节点的父节点
         * 替换法：
         *  找到待删除节点左子树中最大的值与待删除节点替换，并删除原最大值所在节点*/
         if(cur.left == null) { // -左子树为空
             if(cur == root) {
                 // --判断是否为根节点
                 root = cur.right;
             } else if(cur == parent.left) {
                 // --待删除节点位于父节点的左子树
                 parent.left = cur.right;
             } else {
                 // --待删除节点位于父节点的右子树
                 parent.right = cur.right;
             }
         } else if(cur.right == null) { // -右子树为空
             if(cur == root) {
                 // --判断是否为根节点
                 root = cur.left;
             } else if(cur == parent.left) {
                 // --待删除节点位于父节点的左子树
                 parent.left = cur.left;
             } else {
                 // --待删除节点位于父节点的右子树
                 parent.right = cur.left;
             }
         } else { // -左右子树均不为空，使用替换法
             TreeNode tempCur = cur.left;
             TreeNode tempParent = cur;
             while(tempCur.right != null) {
                 tempParent = tempCur;
                 tempCur = tempCur.right;
             }
             cur.val = tempCur.val;
             // -- 此时原左子树最大值节点变为我需要删除的节点，并且其右子树必定为空（上述循环为空停止），故可以采用上述两种删除方式
             if(tempParent.left == tempCur) {
                 tempParent.left = tempCur.left;
             } else {
                 tempParent.right = tempCur.left;
             }
         }
    }

    public void displayByInfixOrder(TreeNode root) {
        /**
         * 以中序遍历的方式打印二叉搜索树（有序）
         * 左根右*/
        // 1 递归出口
        if(root == null) {
            return;
        }

        // 2 递归
        displayByInfixOrder(root.left);
        System.out.print(root.val + " ");
        displayByInfixOrder(root.right);
    }
}




